class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # 定义状态矩阵：dp[i][j] = 有i次机会，有k个球，可以判断多少层（迭代只会用i-1，故此省略i）
        dp = [0] * (k + 1)

        ans = 0
        while dp[k] < n:
            ans += 1
            for j in range(k, 0, -1):
                # 有i个次机会、j个球：
                # 第1次测试可以确定1个；
                # 如果第1次测试碎了，那么剩下j-1个球和i-1次机会，即dp[i-1][j-1]
                # 如果第1次测试没有碎，那么剩下j个球和i-1次机会，即dp[i-1][j]
                # 因为只用到了j和j-1，所以不妨从后向前遍历；这样每次遍历时，dp[j]和dp[j-1]都是i-1的情况
                # 迭代公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+1
                dp[j] = dp[j - 1] + dp[j] + 1
        return ans


if __name__ == "__main__":
    print(Solution().superEggDrop(1, 2))  # 2
    print(Solution().superEggDrop(2, 6))  # 3
    print(Solution().superEggDrop(3, 14))  # 4

    # 自制用例
    print(Solution().superEggDrop(1, 1))  # 1
    print(Solution().superEggDrop(3, 15))  # 5
    print(Solution().superEggDrop(2, 3))  # 2
    print(Solution().superEggDrop(3, 7))  # 2
